package com.zdp.algorithm.linkedlist;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

/**
 * 判断一个链表是否为回文链表
 * @author ZhengDp
 * @Date 2023/2/17 9:27
 */
public class IsPalindrome {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        IsPalindromeImpl3 impl1 = new IsPalindromeImpl3();
        int length = Integer.parseInt(reader.readLine());
        String[] s1 = reader.readLine().split(" ");
        Node head = Node.createNodeList(s1);
        if(impl1.isPalindrome(head,length)){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }
}

/**
 * 解法三 ： 时间复杂度 O(N) 空间复杂度 O(1) ==> 也是进阶问题的解法
 * 主要的思想就是 将链表的后半段翻转
 * 如果链表长度未知的话，可以利用双指针来找到中间结点
 * while( h2.next != null && h2.next.next !=null){
 *     h2 = h2.next.next;
 *     h1 = h1.next;
 * }
 * 奇数 ： h1 -> 中间节点
 * 偶数 ： h1 -> 前半部分最末尾结点
 */
class IsPalindromeImpl3 {

    public Boolean isPalindrome(Node head,int length){
        if(head.next == null || head.next.next == null){
            return true;
        }
        int subLength = length/ 2;
        // 链表长度为奇数，需要跳过中间结点
        int index = length%2 == 0 ? 1 : 0;
        Node cur = head.next;
        // 找到要反转链表的头结点
        while ( index <= subLength) {
            cur = cur.next;
            index ++;
        }
        Node subHead = reverse(cur);
        // 进行比较
        cur = head.next;
        while(subHead != null) {
            if(cur.value != subHead.value) {
                return false;
            }
            cur = cur.next;
            subHead = subHead.next;
        }
        return true;
    }

    /**
     * 反转链表
     * @param head 要反转链表的头节点
     * @return
     */
    private Node reverse(Node head) {
        Node pre = null;
        Node cur = head;
        Node next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

/**
 * 解法二，只需要将前半部分入栈，然后后半部分和栈中的元素进行比较即可
 * 链表长度为奇数 ： 忽略中间结点
 */
class IsPalindromeImpl2 {
    public Boolean isPalindrome(Node head,int length){
        if(head.next == null || head.next.next == null){
            return true;
        }
        int subLength = length/2;
        Node cur = head.next;
        int index = 1;
        Stack<Integer> stack = new Stack<>();
        while( index <= subLength) {
            stack.push(cur.value);
            cur = cur.next;
            index ++;
        }
        if(length %2 != 0){
            cur = cur.next;
        }
        while(cur != null){
            if(stack.pop() != cur.value){
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
}

/**
 * 普通解法，时间复杂度 O(N) 空间复杂度 O(N)
 * 利用栈结构先进后出的特性，遍历链表，将链表的值放入栈
 * 然后同时遍历 栈和链表，判断每个值是否完全一致
 */
class IsPalindromeImpl1 {
    public Boolean isPalindrome(Node head){
        if(head.next == null || head.next.next == null){
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        Node cur = head.next;
        while( cur != null) {
            stack.push(cur.value);
            cur = cur.next;
        }
        cur = head.next;
        while(cur != null) {
            int val1 = cur.value;
            int val2 = stack.pop();
            if(val1 != val2){
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
}
